package Experiment1;

import java.util.Random;

import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation_WeightedQuickUnion implements Percolation{
    
    private int grid[][];
    private int N;
    private WeightedQuickUnionUF uf;
    private int topsite;    //虚拟的渗透顶部格点
    private int bottomsite; //虚拟的渗透底部格点

    public Percolation_WeightedQuickUnion(int N){
        if(N<=0){
            throw new IllegalArgumentException("The number is not within the allowed range");
        }
        
        this.N=N;
        grid=new int[N+1][N+1];

        uf=new WeightedQuickUnionUF(N*N+2);
        topsite=0;
        bottomsite=N*N+1;
    }


    //检查输入的格点坐标是否合法
    private boolean checkInput(int i,int j){
        if(i<1||i>N) throw new IndexOutOfBoundsException(i);
        if(j<1||j>N) throw new IndexOutOfBoundsException(j);
        return true;
    }

    private int calculateIndex(int i,int j){
        return (i-1)*N+j;
    }

    public void open(int i,int j){
        checkInput(i, j);
        this.grid[i][j]=1;

        if(i==1) uf.union(topsite,calculateIndex(i, j));
        else if(grid[i-1][j]==1) uf.union(calculateIndex(i-1, j), calculateIndex(i, j));

        if(i==N) uf.union(bottomsite, calculateIndex(i, j));
        else if(grid[i+1][j]==1) uf.union(calculateIndex(i+1, j), calculateIndex(i, j));

        if(j-1>1&&grid[i][j-1]==1) uf.union(calculateIndex(i, j-1), calculateIndex(i, j));
        if(j+1<=N&&grid[i][j+1]==1) uf.union(calculateIndex(i, j+1), calculateIndex(i, j));

    }


    public boolean isOpen(int i,int j){
        checkInput(i, j);
        if(grid[i][j]!=0) return true;
        return false;
    }

    public boolean isFull(int i,int j){
        checkInput(i, j);
        if(uf.connected(topsite, calculateIndex(i, j))&&uf.connected(bottomsite, calculateIndex(i, j))) return true;
        return false;
    }

    public boolean percolates(){
        if(uf.connected(topsite, bottomsite)) return true;
        return false;
    }    
    
    public static void main(String[] args) {
        System.out.println("开始测试");
        int n=20;
        int grid[][]=new int[n+1][n+1];
        double count=0;

        Percolation_WeightedQuickUnion percolation=new Percolation_WeightedQuickUnion(n);
        Random random=new Random();
        while(percolation.percolates()==false){
            int i=random.nextInt(n)+1;
            int j=random.nextInt(n)+1;
            if(grid[i][j]==1) continue;
            grid[i][j]=1;
            percolation.open(i, j);
            count++;
            System.out.println("格点("+i+","+j+")已设为非阻塞");
        }
        
        double rate=count/(n*n);
        System.out.println(rate);

    }
}

